#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/24 17:05
# ===========================================
#       题目名称： 36. 有效的数独
#       题目地址： https://leetcode.cn/problems/valid-sudoku/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    def isValidSudoku(self, board):
        is_legal = True  # 是否合法
        x, y = 0, 0  # x 层  y 条
        while x < len(board) and y < len(board[0]):
            if board[x][y] != ".":
                # 1. 3 * 3 验证是否合法
                elements = []
                # 0,1,2 3,4,5 6,7,8
                x_s = x - x % 3
                y_s = y - y % 3
                for i in range(x_s, x_s + 3):
                    for j in range(y_s, y_s + 3):
                        if board[i][j] != ".":
                            elements.append(board[i][j])
                if len(elements) != len(set(elements)):
                    is_legal = False
                    break
                # 2. x 验证是否合法
                elements = []
                for i in range(len(board[x])):
                    if board[x][i] != ".":
                        elements.append(board[x][i])
                if len(elements) != len(set(elements)):
                    is_legal = False
                    break
                # 3. y 验证是否合法
                elements = []
                for i in range(len(board)):
                    if board[i][y] != ".":
                        elements.append(board[i][y])
                if len(elements) != len(set(elements)):
                    is_legal = False
                    break
            if x + 1 == len(board[0]):
                x = 0
                y += 1
            else:
                x += 1

        return is_legal


if __name__ == '__main__':
    s = Solution()
    print("True =>", s.isValidSudoku(board=
                                     [["5", "3", ".", ".", "7", ".", ".", ".", "."]
                                         , ["6", ".", ".", "1", "9", "5", ".", ".", "."]
                                         , [".", "9", "8", ".", ".", ".", ".", "6", "."]
                                         , ["8", ".", ".", ".", "6", ".", ".", ".", "3"]
                                         , ["4", ".", ".", "8", ".", "3", ".", ".", "1"]
                                         , ["7", ".", ".", ".", "2", ".", ".", ".", "6"]
                                         , [".", "6", ".", ".", ".", ".", "2", "8", "."]
                                         , [".", ".", ".", "4", "1", "9", ".", ".", "5"]
                                         , [".", ".", ".", ".", "8", ".", ".", "7", "9"]]))
    print("False =>", s.isValidSudoku(board=
                                      [["8", "3", ".", ".", "7", ".", ".", ".", "."]
                                          , ["6", ".", ".", "1", "9", "5", ".", ".", "."]
                                          , [".", "9", "8", ".", ".", ".", ".", "6", "."]
                                          , ["8", ".", ".", ".", "6", ".", ".", ".", "3"]
                                          , ["4", ".", ".", "8", ".", "3", ".", ".", "1"]
                                          , ["7", ".", ".", ".", "2", ".", ".", ".", "6"]
                                          , [".", "6", ".", ".", ".", ".", "2", "8", "."]
                                          , [".", ".", ".", "4", "1", "9", ".", ".", "5"]
                                          , [".", ".", ".", ".", "8", ".", ".", "7", "9"]]))
